#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

void Swap(int* p1, int* p2)
{
    int t = *p1;
    *p1 = *p2;
    *p2 = t;
}
void Adjustown(int* arr, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;

    while (child < n)
    {
        if (child + 1 < n && arr[child + 1] > arr[child])
        {
            child++;
        }

        if (arr[child] > arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int* arr, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        Adjustown(arr, n, i);
    }

    int end = n - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        Adjustown(arr, end, 0);
        end--;
    }
}

void sortColors(int* nums, int numsSize)
{
    HeapSort(nums, numsSize);
}